// https://leetcode.cn/problems/lru-cache/
// Created by ade on 2022/7/28.
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
/*
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * */
#include <iostream>
#include <unordered_map>

using namespace std;

struct Node {
    int key;
    int val;
    Node *next;
    Node *prev;

    Node() : key(0), val(0), next(nullptr), prev(nullptr) {}

    Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}

    Node(int key, int val, Node *next, Node *prev) :key(key), val(val), next(next), prev(prev) {}
};

class LRUCache {
public:
    unordered_map<int, Node *> addrMap; // 数值-映射对应的存储地址

    Node *dummyHead = nullptr;
    Node *dummyTail = nullptr;


    int count = 0;
    int total = 0;

    LRUCache(int capacity) {
        total = capacity;
        dummyHead = new Node(-1,-1);
        dummyTail = new Node(-1,-1);
        dummyHead->next = dummyTail;
        dummyTail->prev = dummyHead;
    }

    int get(int key) {
        if (addrMap.find(key) == addrMap.end()) return -1;

        Node *node = addrMap[key];
        if (node->prev == dummyHead) return node->val;
        moveToHead(node);

        return node->val;
    }

    void put(int key, int value) {
        // 判断当前key值是否已经存在
        // 1.已存在 将该值提到队列的最前端 并返回
        // 2.不存在，新添一个值到队列的头部，count++
        //2.1判断当前存储的个数是否超过总数，如果超过，需要删除队列尾部的节点
        if (addrMap.find(key) != addrMap.end()) {
            Node *node = addrMap[key];
            if(value != node->val) node->val = value;
            if (node->prev == dummyHead) return;
            moveToHead(node);
        } else {
            Node *node = new Node(key, value);
            Node *next = dummyHead->next;
            dummyHead->next = node;
            node->prev = dummyHead;
            node->next = next;
            next->prev = node;
            addrMap[key] = node;
            count++;

            if (count > total) {
                deleteNode();
            }
        }
        show();
    }

    void deleteNode() {
        Node *prev = dummyTail->prev;
        Node * prevPrev = prev->prev;

        addrMap.erase(prev->key);
        prevPrev->next = dummyTail;
        dummyTail->prev = prevPrev;

        delete prev;
        count--;
    }

    void moveToHead(Node *node) {
        Node *prev = node->prev;
        Node *next = node->next;
        Node *headNext = dummyHead->next;
        dummyHead->next = node;
        node->prev = dummyHead;
        node->next = headNext;
        headNext->prev = node;

        prev->next = next;
        next->prev = prev;
    }

    void show() {
        cout << "show:";
        Node *index = dummyHead;
        while (index) {
            cout << index->val << ",";
            index = index->next;
        }
        cout << endl;
    }
};


int main() {
    // ["LRUCache","put","put","get","put","put","get"]
    // [[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]
    LRUCache cache(2);
    cache.put(2, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;
    cache.put(3, 3);
    cout << cache.get(2) << endl;
    cache.put(4, 4);
    cout << cache.count << endl;
    for(auto i : cache.addrMap){
        cout << i.first << "-" << i.second->val << endl;
    }
    cout << cache.get(1) << endl;
    cout << cache.get(3) << endl;
    cout << cache.get(4) << endl;
    return 0;
}

